package com.mdnote.structure.sort;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/8/27
 * @description 基数排序
 */
public class RedixSort {

    public static void sort(int[] source) {
        
        // 找到最大值
        int max = 0;
        for (int i = 0; i < source.length; i++) {
            if (source[i] > max) {
                max = source[i];
            }
        }
        
        // 最大位数
        int maxDigit = (max + "").length();

        // 基数排序，先创建10个桶
        int[][] bucket = new int[10][source.length];
        // 创建索引
        int[] bucketCursor = new int[10];
        // 控制排序的位置  个位  十位  百位
        for (int i = 0, n = 1; i < maxDigit; i++, n *= 10) {

            // 先把数组放到桶里
            for (int j = 0; j < source.length; j++) {
                int bucketIndex = source[j] / n % 10;
                bucket[bucketIndex][bucketCursor[bucketIndex]] = source[j];
                bucketCursor[bucketIndex]++;
            }

            // 按顺序从桶里拿出数据放回数组中
            int sourceIndex = 0;
            for (int j = 0; j < bucket.length; j++) {
                if (bucketCursor[j] != 0) {
                    // 有数据，可拿
                    for (int k = 0; k < bucketCursor[j]; k++) {
                        source[sourceIndex] = bucket[j][k];
                        sourceIndex++;
                    }
                }
                // 把bucketCursor清零
                bucketCursor[j] = 0;
            }
        }
    }

    public static void main(String[] args) {
        int[] data = {22, 33, 77, 11, 12};
        sort(data);
        System.out.println(Arrays.toString(data));
    }
}
